Hill Climbing

Hill Climbing algorithms are based on iterative improvement.

The problem space is viewed as an n-dimensional landscape, and the height above the surface is the fitness value returned by the evaluation function at that point. The analogy is to climbing a hill in the fog: try one step in each direction, and keep the one which takes you higher.

The same technique is sometimes referred to as gradient descent, with the analogy of a ball rolling down hill. Simply invert the visualized surface.

Real-world surfaces are often much more complex, with many local maxima:

And present complexities such as saddle points and plateaus:

In each of these cases the algorithm may become stuck at a local maximum. Several partial solutions for these difficulties exist. One is to run many searches in parallel, each starting from a different random location. Another is simulated annealing, in which downhill steps are allowed during the early stages of the search.

back index forward